package arithmetic1.divideAndRule;

/*
   分治算法解决汉若塔问题:
    将n个盘看成最下面的一个盘和上面的(n-1)个盘，然后将上面的n-1个盘移动到B塔，将最下面的盘移动到C塔，最后将n-1个盘从B塔移到C塔
 */
public class HanIfTower {
//    static int count=0;
    public static void main(String[] args) {
        hanIfTower(4,'A','B','C');
//        System.out.println(count);
    }

    /**
     *
     * @param n: 盘子个数
     * @param a: 要移动盘子的起始位置
     * @param b：中间盘子
     * @param c：要移动盘子的目标位置
     */
    public static void hanIfTower(int n,char a,char b,char c){
        if(n>1){    //盘子个数大于1
            //将上面的n-1个盘从A塔移动到B塔
            hanIfTower(n-1,a,c,b);
            //将最下面的盘子从A塔移动到C塔
            hanIfTower(1,a,b,c);
            //将n-1个盘子从B塔移动到C塔
            hanIfTower(n-1,b,a,c);
        }else {
            System.out.println(a+"-->"+c);
        }
    }
}
